/**
 * @Author ZhangCuirong
 * @Date 2025/9/16 10:47
 * @description:
 */
public class Solution887 {
    public int superEggDrop(int k, int n) {
        // dp[i][j]：i层楼，j个鸡蛋，最少尝试次数
        int[][] dp = new int[n + 1][k + 1];

        // 初始条件1：1层楼，任意鸡蛋数→1次
        for (int j = 1; j <= k; j++) {
            dp[1][j] = 1;
        }

        // 初始条件2：1个鸡蛋，i层楼→i次
        for (int i = 1; i <= n; i++) {
            dp[i][1] = i;
        }

        // 填充dp表（i从2层开始，j从2个鸡蛋开始）
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                // 尝试在第x层扔鸡蛋（x范围1~i）
                for (int x = 1; x <= i; x++) {
                    // 碎了：x-1层，j-1个鸡蛋
                    // 没碎：i-x层，j个鸡蛋
                    int current = Math.max(dp[x - 1][j - 1], dp[i - x][j]) + 1;
                    // 取最小值
                    dp[i][j] = Math.min(dp[i][j], current);
                }
            }
        }

        return dp[n][k];
    }
    public int superEggDrop2(int k, int n) {
        // dp[m][k] = 有k个鸡蛋，最多试m次，能确定的最高楼层数
        int[][] dp = new int[n + 1][k + 1];
        int m = 0; // 尝试次数

        // 当最高可确定楼层数 < n时，继续增加尝试次数
        while (dp[m][k] < n) {
            m++;
            // 1个鸡蛋，m次最多确定m层
            dp[m][1] = m;
            // 遍历鸡蛋数量（从2到k）
            for (int j = 2; j <= k; j++) {
                // 状态转移：碎了的层数 + 没碎的层数 + 当前楼层
                dp[m][j] = dp[m - 1][j - 1] + dp[m - 1][j] + 1;
            }
        }
        return m;
    }
    public static void main(String[] args) {
        Solution887 solution = new Solution887();
        System.out.println(solution.superEggDrop(1, 2));
        System.out.println(solution.superEggDrop(2, 6));
        System.out.println(solution.superEggDrop(3, 14));
    }
}
